package com.school.chapter02.tree_;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

@SuppressWarnings({"all"})
class BinaryTree_2<T> {
    private BinaryTree_2 root;

    public static void main(String args[]) {
        int[] preOrders = new int[]{1, 2, 4, 8, 5, 3, 6, 7};
        int[] inOrders = new int[]{8, 4, 2, 5, 1, 6, 3, 7};
        BinaryTree_2 b = buildTree(preOrders, inOrders);
        System.out.printf("前序遍历:");
        b.preOrder();
        System.out.printf("\n中序遍历:");
        b.infixOrder();
        System.out.printf("\n后序遍历:");
        b.postOrder();
        System.out.printf("\n层序遍历:");
        b.LayerOrder(b);
        System.out.printf("\nb树有%d个叶子\n", b.leaves());
        System.out.printf("树的高度是：%d", b.height());
        System.out.println("将树中的每个节点的孩子对换位置");
        b.reflect();
        System.out.printf("前序遍历:");
        b.preOrder();
        System.out.printf("\n中序遍历:");
        b.infixOrder();
        System.out.printf("\n后序遍历:");
        b.postOrder();
        System.out.printf("\n层序遍历:");
        b.LayerOrder(b);

    }

    private Object data;
    BinaryTree_2[] elements = new BinaryTree_2[40];// 层次遍历时保存各个节点
    int front;// 层次遍历时队首
    int rear;// 层次遍历时队尾
    private BinaryTree_2 left;
    private BinaryTree_2 right;

    public BinaryTree_2(final T data) {
        this(data, null, null);
    }

    public BinaryTree_2(final T data, final BinaryTree_2 left, final BinaryTree_2 right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
    public BinaryTree_2(BinaryTree_2 root){
        this.root = root;
    }

    public int getData() {
        return (int) data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTree_2 getLeft() {
        return left;
    }

    public void setLeft(BinaryTree_2 left) {
        this.left = left;
    }

    public BinaryTree_2 getRight() {
        return right;
    }

    public void setRight(BinaryTree_2 right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return data.toString();
    }

    public void delNode(int no) {
        if (this.left != null && (int) this.left.data == no) {
            this.left = null;
            return;
        }
        if (this.right != null && (int) this.right.data == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    //前序遍历
    public void preOrder() {
        System.out.print(this + " ");
        if (this.left != null) this.left.preOrder();
        if (this.right != null) this.right.preOrder();
    }

    //中序遍历
    public void infixOrder() {
        if (this.left != null) this.left.infixOrder();
        System.out.print(this + " ");
        if (this.right != null) this.right.infixOrder();
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) this.left.postOrder();
        if (this.right != null) this.right.postOrder();
        System.out.print(this + " ");
    }

    //层序遍历
    // 层次遍历二叉树
    public void LayerOrder(BinaryTree_2 parent) {
        elements[0] = parent;
        front = 0;
        rear = 1;
        while (front != rear) {
            try {
                if (elements[front].data != null) {
                    System.out.print(elements[front].data + " ");
                    if (elements[front].left != null)
                        elements[rear++] = elements[front].left;
                    if (elements[front].right != null)
                        elements[rear++] = elements[front].right;
                    front++;
                }
            } catch (Exception e) {
                break;
            }
        }
    }

    // 返回树的叶节点个数
    public int leaves() {
        //根节点为空
        if (this == null)
            return 0;
        if (left == null && right == null)
            return 1;
        return (left == null ? 0 : left.leaves()) + (right == null ? 0 : right.leaves());
    }

    // 结果返回树的高度
    public int height() {
        int heightOfTree;
        if (this == null)
            return -1;
        int leftHeight = (left == null ? 0 : left.height());
        int rightHeight = (right == null ? 0 : right.height());
        heightOfTree = leftHeight > rightHeight ? leftHeight : rightHeight;
        return 1 + heightOfTree;
    }

    // 如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
    public int level(Object object) {
        int levelInTree;
        if (this == null)
            return -1;
        if (object == data)
            return 1;// 规定根节点为第一层
        int leftLevel = (left == null ? -1 : left.level(object));
        int rightLevel = (right == null ? -1 : right.level(object));
        if (leftLevel < 0 && rightLevel < 0)
            return -1;
        levelInTree = leftLevel >= 0 ? leftLevel : rightLevel;
        return 1 + levelInTree;
    }

    // 将树中的每个节点的孩子对换位置
    public void reflect() {
        if (this == null)
            return;
        if (left != null)
            left.reflect();
        if (right != null)
            right.reflect();
        BinaryTree_2 temp = left;
        left = right;
        right = temp;
    }

    //求节点双亲
    public BinaryTree_2 getParent(BinaryTree_2 root, BinaryTree_2 current) {
        BinaryTree_2 p = null;
        if (root == null) {
            return null;
        }
        //返回条件
        if (root.right == current || root.left == current) {//若左右任一个子树是待求双亲的节点，则此节点为答案
            return root;
        }
        //往左找
        p = getParent(root.left, current);
        if (p != null) {
            return p;
        }
        //往右找
        else {
            return getParent(root.right, current);
        }
    }


    //通过前序、中序遍历结果构建一个棵树
    private static BinaryTree_2 buildTree(int[] preOrders, int[] inOrders) {
        if (preOrders.length == 0 || inOrders.length == 0) {
            return null;
        }
        BinaryTree_2 tree = new BinaryTree_2(preOrders[0]);
        int index = search(0, inOrders.length, inOrders, tree.getData());
        tree.setLeft(buildTree(Arrays.copyOfRange(preOrders, 1, index + 1),
                Arrays.copyOfRange(inOrders, 0, index)));
        tree.setRight(buildTree(Arrays.copyOfRange(preOrders, index + 1, preOrders.length),
                Arrays.copyOfRange(inOrders, index + 1, inOrders.length)));
        return tree;
    }

    private static int search(int start, int end, int[] inOrders, int data) {
        for (int i = start; i < end; i++) {
            if (data == inOrders[i]) {
                return i;
            }
        }
        return -1;
    }


}
